// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
)

// 将最大整数值设置为 MAX
const MAX = math.MaxInt32

func Prims(graph [][]int, n int) int {
	// 创建三个切片以跟踪键值、最小生成树和访问的顶点
	key := make([]int, n)
	mst := make([]int, n)
	visited := make([]bool, n)

	less
	Copy code
	// 为每个顶点初始化键值和最小生成树数组
	for i := 0; i < n; i++ {
		key[i] = MAX
		mst[i] = -1
	}

	// 将第一个顶点的键值设置为 0 并将其标记为已访问
	key[0] = 0
	mst[0] = -1

	// 遍历除最后一个顶点之外的所有顶点
	for i := 0; i < n-1; i++ {
		// 找到未访问过的具有最小键值的顶点
		minIndex := findMinVertex(key, visited, n)
		visited[minIndex] = true

		// 如有必要，更新相邻顶点的键值和最小生成树数组
		for j := 0; j < n; j++ {
			if graph[minIndex][j] != 0 && !visited[j] && graph[minIndex][j] < key[j] {
				key[j] = graph[minIndex][j]
				mst[j] = minIndex
			}
		}
	}

	// 计算最小生成树的总权重
	sum := 0
	for i := 1; i < n; i++ {
		sum += graph[i][mst[i]]
	}
	return sum
}

func findMinVertex(key []int, visited []bool, n int) int {
	min := MAX
	minIndex := -1
	for i := 0; i < n; i++ {
		if visited[i] == false && key[i] < min {
			min = key[i]
			minIndex = i
		}
	}
	return minIndex
}

func main() {
	graph := [][]int{{0, 2, 0, 6, 0},
		{2, 0, 3, 8, 5},
		{0, 3, 0, 0, 7},
		{6, 8, 0, 0, 9},
		{0, 5, 7, 9, 0},
	}
	fmt.Println("最小生成树的权重是:", Prims(graph, 5))
}

//$ go run prim.go
//最小生成树的权重是: 16
